package com.gxc.dynamic;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 快递公司每日早晨，给每位快递员推送需要送到客户手中的快递以及路线信息，快递员自己又查找了一些客户与客户之间的路线距离信息，请你依据这些信息，给快递员设计一条最短路径，告诉他最短路径的距离。
 *
 * 注意：
 *
 * 不限制快递包裹送到客户手中的顺序，但必须保证都送到客户手中
 * 用例保证一定存在投递站到每位客户之间的路线，但不保证客户与客户之间有路线，客户位置及投递站均允许多次经过
 * 所有快递送完后，快递员需回到投递站
 * 输入描述
 * 首行输入两个正整数n、m
 *
 * 接下来 n 行，输入快递公司发布的客户快递信息，格式为：
 *
 * 客户id 投递站到客户之间的距离distance
 *
 * 再接下俩的 m 行，是快递员自行查找的客户与客户之间的距离信息，格式为
 *
 * 客户id1 客户id2 distance
 *
 * 在每行数据中，数据与数据之间均以单个空格分隔
 *
 * 规格：
 *
 * 0 < n ≤ 10
 * 0 ≤ m ≤ 10
 * 0 < 客户id ≤ 1000
 * 0 < distance ≤ 10000
 * 输出描述
 * 最短路径距离，如无法找到，请输出-1
 */
public class Courier {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 读取客户数量
        int M = scanner.nextInt(); // 读取客户之间的路线数量

        // 初始化图，所有距离默认设为 -1（表示无路径）
        int[][] graph = new int[N + 1][N + 1];
        for (int[] row : graph) Arrays.fill(row, -1);
        for (int i = 0; i <= N; i++) graph[i][i] = 0; // 自己到自己的距离设为 0

        // 使用 Map 离散化 ID
        Map<Integer, Integer> mp = new HashMap<>();

        // 读取投递站到客户的距离
        for (int i = 0; i < N; i++) {
            int id = scanner.nextInt();
            int distance = scanner.nextInt();
            mp.put(id, i + 1); // 记录客户 ID 对应的索引
            graph[0][mp.get(id)] = distance;
            graph[mp.get(id)][0] = distance;
        }

        // 读取客户之间的距离
        for (int i = 0; i < M; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            int distance = scanner.nextInt();
            graph[mp.get(start)][mp.get(end)] = distance;
            graph[mp.get(end)][mp.get(start)] = distance;
        }

        // Floyd-Warshall 算法计算最短路径
        for (int k = 0; k <= N; k++) {
            for (int i = 0; i <= N; i++) {
                for (int j = 0; j <= N; j++) {
                    if (graph[i][k] == -1 || graph[k][j] == -1) continue;
                    if (graph[i][j] == -1) graph[i][j] = graph[i][k] + graph[k][j];
                    else graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }

        // 状态压缩 DP，dp[mask][cur] 表示访问 mask 对应的所有客户后，最后停在 cur 的最短路径
        int[][] dp = new int[1 << N][N + 1];
        for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
        dp[0][0] = 0; // 从起点出发

        for (int mask = 0; mask < (1 << N); mask++) {
            for (int cur = 0; cur <= N; cur++) {
                if (dp[mask][cur] == Integer.MAX_VALUE) continue;
                for (int next = 0; next <= N; next++) {
                    if (graph[cur][next] == -1) continue;
                    if (next == 0) {
                        dp[mask][next] = Math.min(dp[mask][next], dp[mask][cur] + graph[cur][next]);
                    } else {
                        int nextMask = mask | (1 << (next - 1));
                        dp[nextMask][next] = Math.min(dp[nextMask][next], dp[mask][cur] + graph[cur][next]);
                    }
                }
            }
        }

        // 计算最终结果，遍历所有可能的终点
        int end = (1 << N) - 1;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i <= N; i++) {
            if (dp[end][i] != Integer.MAX_VALUE && graph[i][0] != -1) {
                res = Math.min(res, dp[end][i] + graph[i][0]);
            }
        }

        // 输出结果
        System.out.println(res);
    }
}
